package com.cjl.interview150.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class BinaryTreePractice {
    /**
     * 100. 相同的树
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 深度优先搜索
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left,q.left ) && isSameTree(p.right, q.right);
        }
    }

    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeRecur(0, 0, inorder.length - 1,map,preorder);
    }

    private TreeNode buildTreeRecur(int root, int left, int right, HashMap<Integer, Integer> map, int[] preorder) {
        if (left > right) {
            return null;
        }
        // 建立根节点
        TreeNode rootNode = new TreeNode(preorder[root]);
        // 划分根节点,左右子树,获取根节点在中序遍历的位置
        int i = map.get(preorder[root]);
        // 开启左右子树递归
        rootNode.left = buildTreeRecur(root + 1, left, i - 1, map, preorder);
        // `i - left + root + 1`含义为 `根节点索引 + 左子树长度 + 1`
        rootNode.right = buildTreeRecur(root + i - left + 1, i + 1, right, map, preorder);
        return rootNode;
    }

    /**
     * 114. 二叉树展开为链表
     * @param root
     */
    public void flatten(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<>();
        // 以线序遍历的顺序将各个节点加入链表
        preorderTraversal(root,list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode cur = list.get(i);
            TreeNode pre = list.get(i - 1);
            // 之前的节点左孩子置空,右孩子为当前节点
            pre.left = null;
            pre.right = cur;
        }
    }
    private void preorderTraversal(TreeNode root, ArrayList<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left,list);
            preorderTraversal(root.right,list);
        }
    }

    /**
     * 129. 求根节点到叶节点数字之和
     * @param root
     * @return
     */
    public int sumNumbers(TreeNode root) {
        return sumNumbersHelper(root, 0);
    }

    private int sumNumbersHelper(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int temp = sum * 10 + root.val;
        // 遇到叶子节点就返回temp
        if (root.left == null && root.right == null) {
            return temp;
        }
        return sumNumbersHelper(root.left, temp) + sumNumbersHelper(root.right, temp);
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 创建双端队列和结果集合
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        // 加入头元素
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            // 创建临时队列存储这一行的元素
            LinkedList<Integer> temp = new LinkedList<>();
            // 利用队列中元素的个数确定当前需要poll出的元素数量,并加入每个节点的左右子树
            int size = queue.size();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                // 如果是奇数层从尾部添加,偶数层则从头部添加
                if (res.size() % 2 == 0) {
                    temp.addLast(node.val);
                } else {
                    temp.addFirst(node.val);
                }
                // 如果有左右孩子则加入
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(temp);
        }
        return res;
    }

    /**
     * 230. 二叉搜索树中第K小的元素
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        // 加入二叉搜索树的中序序列
        kthSmallestInorderTraversal(root,list);
        return list.get(k - 1);
    }

    private void kthSmallestInorderTraversal(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        // 中序遍历
        kthSmallestInorderTraversal(root.left,list);
        list.add(root.val);
        kthSmallestInorderTraversal(root.right,list);
    }


}

/**
 * 173. 二叉搜索树迭代器
 */
class BSTIterator {
    // 利用中序遍历序列解决
    private int index;
    private ArrayList<Integer> list;

    public BSTIterator(TreeNode root) {
        index = 0;
        list = new ArrayList<>();
        // 构造中序遍历的序列
        inorderTraversal(root, list);
    }

    private void inorderTraversal(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        // 中序遍历:左中右
        inorderTraversal(root.left, list);
        list.add(root.val);
        inorderTraversal(root.right,list);
    }

    public int next() {
        // 获取一个元素之后序号加一
        return list.get(index++);
    }

    public boolean hasNext() {
        return index < list.size();
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
